\section{素 数 分 布}

\begin{frame}{素数分布}
素数的分布问题一直是人们所关心的。 我们已证明素数有无限多。 下面要证明的 $\sum 1 / p$ 发散， 说明素数 $p$ 不很稀少 (例如， 比 $\left\{2^{n}\right\}$ 稠密), 所使用的方法很有典型性。

\begin{theorem}%定理1
$\displaystyle\sum_{p} \frac{1}{p}$ 发散(其中求和是对正素数).
\end{theorem}

\begin{proof}
 记小于 $n$ 的正素数为 $p_{1}, \cdots, p_{k}$, 共 $k=k(n)$ 个 ($p_{1}=2, p_{2}=3, \cdots$). 考虑乘积
\[
  \lambda(n)=\prod_{i=1}^{k} \frac{1}{1-\frac{1}{p_{i}}}=\prod_{i=1}^{k}\left(1+\frac{1}{p_{i}}+\frac{1}{p_{i}^{2}}+\frac{1}{p_{i}^{3}}+\cdots\right).
\]
这里用到 $(1-x)^{-1}=1+x+x^{2}+\cdots$, 将上式右边按分配律乘开， 得到和式
\[
\lambda(n)=\sum_{a_{1}, \cdots, a_{k}} \frac{1}{p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}},
\]
其中求和是对 $a_{1}, \cdots, a_{k}$ 的所有可能非负整数值。 特别知， 和式中的项有 $1$ (即 $a_{i}$ 均取 $0$), $\frac{1}{2}$ (即取 $a_{1}=1$, 其余 $a_{i}=0$), $\frac{1}{3}$, 等等。 \end{proof}
\end{frame}

\begin{frame}
  \begin{proof}[续]
故
\[
\lambda(n)>1+\frac{1}{2}+\frac{1}{3}+\cdots \rightarrow \infty \quad(\text {当~} n \rightarrow \infty)
\]
(这证明了素数有无限多). 再看对数， 有
\[
  \log \lambda(n)=-\sum_{i=1}^{k} \log \left(1-\frac{1}{p_{i}}\right)=\sum_{i=1}^{k} \sum_{m=1}^{\infty} \frac{1}{m p_{i}^{m}}.
\]
将 $m=1$ 的情形分离出， 得到
\[
  \log \lambda(n)=\sum_{i=1}^{k} \frac{1}{p_{i}}+\sum_{i=1}^{k} \sum_{m=2}^{\infty} \frac{1}{m p_{i}^{m}}.
\]
因 $\sum_{m=2}^{\infty} \frac{1}{m p_{i}^{m}}<\sum_{m=2}^{\infty} \frac{1}{p_{i}^{m}}=\frac{1}{p_{i}^{2}}\left(1-\frac{1}{p_{i}}\right)^{-1} \leqslant \frac{2}{p_{i}^{2}}$, 故
\[
  \log \lambda(n)<\sum_{i=1}^{k(n)} \frac{1}{p_{i}}+\sum_{i=1}^{k(n)} \frac{2}{p_{i}^{2}}.
\]
因 $\sum_{n=1}^{\infty} \frac{1}{n^{2}}$ 收敛， 故 $\sum_{i=1}^{\infty} \frac{2}{p_{i}^{2}}$ 收敛。 今若 $\sum_{i=1}^{\infty} \frac{1}{p_{i}}$ 也收敛 (即 $\sum_{p} \frac{1}{p}$ 收敛), 则
\(
\log \lambda(n)<M \text { (对某常数  $M$), }
\)
从而 $\lambda(n)<\mathrm{e}^{M}$, 与 $\lambda(n) \rightarrow \infty$ (当 $n \rightarrow \infty$) 矛盾。
\end{proof}
\end{frame}

\begin{frame}
上述思想源自 Euler, 是解析方法的源头。 它用一个乘积
\[
\prod_{p}(1-1 / p)^{-1}=\prod_{p} \sum_{j} 1 / p^{j}
\]
表示一个和式 $\sum_{a_{1}, \cdots, a_{k}} \frac{1}{p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}} \approx \sum_{n} \frac{1}{n}$. 发展之后， 可将 $1 / p$ 换为 $a(p) / p^{s}$, 将 $1 / n$ 换为 $a(n) / n^{s}$ (其中 $a(n)$ 为完全积性函数). 此类乘积称为 Euler 乘积， 和式称为 \emph{Dirichlet 级数}。

用这种思想方法， 可以证明定理 1 到多项式的模拟结果。 设 $\mathbb{F}_{q}$ 为 $q$ 个元素的域 (例如 $\mathbb{Z} / p \mathbb{Z}$ 是 $p$ (素数)个元素的域), 考虑系数属于 $\mathbb{F}_{q}$ 的多项式集合 (环) $\mathbb{F}_{q}[X]$, 则有
\begin{theorem*}[定理 A]
  $\sum_{p(X)} q^{-\operatorname{deg} p(x)}$ 发散， 其中求和对所有首一不可约多项式
\(
  p(X) \in \mathbb{F}_{q}[X].
\)
\end{theorem*}

\begin{proof}
  见 Ireland 和 Rosen 《A classical introduction to modern number theory》第二章定理 4.
\end{proof}

整数和多项式常有类似的结果。 进而， 代数数域和环与代数函数域和环常
有类似的结果， 代数数论与代数几何常有类似的结果。 它们的发展常互相推动参照，有共同的理论和思想基础。


\end{frame}

\begin{frame}
  \begin{proposition}
    记 $\pi(x)$ 为不超过正实数 $x$ 的正素数个数 $(x \geqslant 2)$, 则
    \[
      \pi(x) \geqslant \log (\log x).
    \]
  \end{proposition}

\begin{proof}
 记 $p_{n}$ 为第 $n$ 个正素数， 则因为 $p_{1} \cdots p_{n}+1$ 的素因子必异于 (从而大于) $p_{1}, \cdots, p_{n}$, 故知
\(
  p_{1} \cdots p_{n}+1 \geqslant p_{n+1}.
\)
易归纳得$p_n<2^{2^{n}}$; 诚然，现 $p_{1}=2<2^{2^{1}}$, 而若 $p_{k}<2^{2^{k}}(k \leqslant n)$, 可得
\[
  p_{n+1} \leqslant p_{1} \cdots p_{n}+1 \leqslant 2^{21} \cdots 2^{2 n}+1=2^{2 n+1-2}+1<2^{2^{n+1}}.
\]
于是 $\pi\left(2^{2 n}\right) \geqslant n$. 对 $x>\mathrm{e}^{\mathrm{e}}$, 取 $n$ 使 $\mathrm{e}^{\mathrm{e}^{n-1}}<x \leqslant \mathrm{e}^{\mathrm{e}^{n}}$. 
若 $n > 3$, 则 $\mathrm{e}^{n-1}>2^{n}$, 故
\[
  \pi(x) \geqslant \pi\left(\mathrm{e}^{\mathrm{e}^{n-1}}\right) \geqslant \pi\left(\mathrm{e}^{2^{n}}\right) \geqslant \pi\left(2^{2^{n}}\right) \geqslant n \geqslant \log \log x.
\]
这对 $x>\mathrm{e}^{\mathrm{e}^3}$ 证明了定理。 
当 $5\leqslant x \leqslant \mathrm{e}^{\mathrm{e}^3}$ 时，$\pi(x)\geqslant 3 \geqslant \log\log x$; 当$2\leqslant x<5$时，$\pi(x)>1\geqslant \log\log x$ (注意到$\mathrm{e}^{\mathrm{e}}>2.5^2>5$).
证毕。
\end{proof}

\begin{theorem}%定理2
记 $\pi(x)$ 为不超过正整数 $x$ 的正素数个数， 则
\[
  \pi(x) \geqslant \log x /(2 \log 2).
\]
\end{theorem}
\end{frame}

\begin{frame}


\begin{proof}
  以 $\gamma(n)$ 记 $n$ 的素因子集合。 对素数的任一集合 $S$, 以 $f_{S}(x)$ 记满足 $n \leqslant x$ 且 $\gamma(n) \subset S$ 的正整数 $n$ 的个数，即$f_S(x)=\sharp \left\{ n\in \NN \mid n\leqslant x, \gamma(n)\subset S \right\}$. 表这些 $n$ 为 $n=m^{2} n_{1}$, 其中 $n_{1}$ 为无平方因子整数。 于是
\[
  m \leqslant \sqrt{x},
\]
故正整数$m$的可能性不超过$\sqrt{x}$个。
$n_{1}$ 为 $S$ 的子集， 有 $2^{\# S}=2^{s}$ 种可能 ($s=\sharp S$)。 故 $f_{S}(x) \leqslant 2^{s} \sqrt{x}$. 记 $\pi(x)=k$, 则 $p_{k+1}>x$. 若取 $S=\left\{p_{1}, \cdots, p_{k}\right\}$, 则显然 $f_{S}(x)=x$. 故
\[
  x=f_{S}(x) \leqslant 2^{k} \sqrt{x}=2^{\pi(x)} \sqrt{x}.
\]
\end{proof}

尽管命题1和定理2给出了$\pi(x)$的两个下界，这两个下界太小，因此命题1和定理2是很粗的估计。

为了给出 $\pi(x)$ 的上界， 记 $\theta(x)=\sum_{p \leqslant x} \log p$ 
(求和是对正素数 $p \leqslant x$), $\theta(1)= 0$. 
注意 $\theta(x) \leqslant \pi(x) \log x$.

\begin{theorem}%定理3
(1) $\theta(x)<(4 \log 2) x$.

(2) 存在常数 $c_{1}, c_{2}$, 使得 ($x \geqslant 2$ 时) 有
\[
c_{2} \frac{x}{\log x}<\pi(x)<c_{1} \frac{x}{\log x} .
\]
特别知， $\pi(x) / x \rightarrow 0$ (当 $x \rightarrow \infty$).
\end{theorem}
\end{frame}

\begin{frame}

\begin{proof}
 (1) $\binom{2 n}{n}=(n+1) \cdots(2 n) / n!$  可被所有满足$n<p<2 n$的素数 $p$ 整除。 故
\[
\begin{aligned}
  (1+1)^{2 n}&= \sum_{j=0}^{2 n} \binom{2 n}{j}>\binom{2 n}{n}>\prod_{n<p<2 n} p, \\
2 n \log 2 &>\sum_{n<p<2 n} \log p=\theta(2 n)-\theta(n).
\end{aligned}
\]
对 $n=1,2,4,8, \cdots, 2^{m-1}$ 求和， 得
\[
  \theta\left(2^{m}\right)<(\log 2)\left(2^{m+1}-2\right)<(\log 2) 2^{m+1}.
\]
取 $m$ 使 $2^{m-1}<x \leqslant 2^{m}$, 得
\[
  \theta(x)<\theta\left(2^{m}\right)<(\log 2) 2^{m+1}=(4 \log 2) 2^{m-1}<(4 \log 2) x.
\]

 (2) 因
\[
\begin{gathered}
  \theta(x) \geqslant \sum_{\sqrt{x}<p \leqslant x} \log p \geqslant(\log \sqrt{x})[\pi(x)-\pi(\sqrt{x})]=\frac{1}{2} \log x[\pi(x)-\pi(\sqrt{x})],
\quad\text{故} \\
\pi(x) \leqslant 2 \theta(x) / \log x+\sqrt{x} \leqslant(8 \log 2) x / \log x+\sqrt{x} .
\end{gathered}
\]
因 $\sqrt{x}<2 x / \log x$ (当 $x \geqslant 2$), 取 $c_{1}=8 \log 2+2$ 即可。
\end{proof}

\end{frame}

\begin{frame}

  \begin{proof}[续]
为求 $\pi(x)$ 的下限， 注意
\[
\begin{aligned}
  \binom{2 n}{n}&= \frac{n+1}{1}\cdot \frac{n+2}{2}\cdot \cdots \cdot \frac{2 n}{n} \geqslant 2^{n}, \\
  v_{p}\left(\binom{2 n}{n}\right)&= v_{p}\left(\frac{(2 n)!}{(n!)^{2}}\right)=\sum_{j=1}^{t_{p}}\left(\left\lfloor\frac{2 n}{p^{j}}\right\rfloor-2\left\lfloor\frac{n}{p^{j}}\right\rfloor\right).
\end{aligned}
\]
这里用到下面的引理1， $v_{p}(a)$ 是$a$的$p$-进赋值， $t_{p}$ 是使 $p^{t_{p}} \leqslant 2 n$ 的最大正整数，即 $t_{p}=\lfloor\log 2 n / \log p\rfloor$. 
因 $\lfloor 2 x\rfloor-2\lfloor x\rfloor=0$ 或 $1$ (对整数$m$, $0\leqslant \lfloor mx\rfloor - m\lfloor x\rfloor\leqslant m-1$), 得
\[
  \begin{gathered}
    v_{p}\left(\binom{2 n}{n}\right) \leqslant t_{p}=\lfloor\log 2 n / \log p\rfloor, \qquad \text{故}\\
    2^{n} \leqslant \binom{2 n}{n} \leqslant \prod_{p<2 n} p^{t_{p}}, \\
n \log 2 \leqslant \sum_{p<2 n} t_{p} \log p=\sum_{p<2 n} \lfloor\log 2 n / \log p\rfloor \log p.
\end{gathered}
\]
若 $p>\sqrt{2 n}$, 即 $\log p>\frac{1}{2} \log 2 n$, 则 $\lfloor\log 2 n / \log p\rfloor=1$, 故
\[
  n \log 2 \leqslant \sum_{p<\sqrt{2 n}}\lfloor\log 2 n / \log p\rfloor \log p+\sum_{2 n>p>\sqrt{2 n}} \log p<\sqrt{2 n} \log 2 n+\theta(2 n).
\]
\end{proof}

\end{frame}

\begin{frame}

  \begin{proof}[续]
    故得 $\theta(2 n)>n \log 2-\sqrt{2 n} \log 2 n$. 因 $(\sqrt{2 n} \log 2 n) / n \rightarrow 0$ (当 $n \rightarrow \infty$时，由L'Hôpital法则知$(\log n)/\sqrt{n}\rightarrow 0$), 故 $\theta(2 n)>$ $M n$ (对某正常数 $M$ 和充分大 $n$). 对充分大的 $x$, 记 $2 n \leqslant x \leqslant 2 n+1$, 则
\[
\theta(x) \geqslant \theta(2 n)>M n \geqslant M(x-1) / 2>C x
\]
(对某 $C$). 故存在常数 $c_{2}$ 使 $\theta(x)>c_{2} x$ 对所有 $x \geqslant 2$. 因
\[
  \theta(x)=\sum_{p \leqslant x} \log p \leqslant \pi(x) \log x,
\]
故
\[
  \pi(x) \geqslant \frac{\theta(x)}{\log x}>c_{2} \frac{x}{\log x}.
\]
\end{proof}

  \pause
  \begin{lemma}%定理4
  \[
  v_{p}(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\cdots
\]
%其中 $\lfloor\alpha\rfloor$ 表示实数 $\alpha$ 的整数部分， 即是$\lfloor\alpha\rfloor$满足 $k \leqslant \alpha$ 的最大整数$k$. 
%$\lfloor\alpha\rfloor$ 也称为\emph{地板函数}， 有时也记为 $[\alpha]$; $n!=1 \cdot 2 \cdot 3 \cdots n$ 为正整数 $n$ 的阶乘; $p$ 为正素数。
\end{lemma}

例如， 要求 $11!=1 \cdot 2 \cdots 11$ 中 $p=2$ 的指数。 在 $1,2, \cdots, 11$ 中， 含因子 $2$ 的有： $2,4,6,8,10$, 共 $5$ 个 $(\lfloor 11 / 2\rfloor=5)$; 含因子 4 的有 $4,8$ 两个; 含因子 $8$ 的有 $8$ 这一个。 故 $11!$中 $2$ 的指数为 $5+2+1=8$, 即 $2^{8}~\|~11!$.
\end{frame}

\begin{frame}

 \begin{proof}
  设 $1$ 到 $n$ 之间的整数中含因子 $p$ 的有 $k$ 个， 即 $1 \leqslant p, 2 p, \cdots, k p \leqslant n$,而 $(k+1) p>n$. 故 $k \leqslant n / p<k+1$, 即 $k=\left\lfloor\frac{n}{p}\right\rfloor$. 
\pause
  同理， $1$ 到 $n$ 之间整数中含因子 $p^{2}$ 的有 $k_{2}$ 个， 即 $p^{2}, 2 p^{2}, \cdots, k_{2} p^{2} \leqslant n, n<\left(k_{2}+1\right) p^{2}, k_{2}=\left\lfloor\frac{n}{p^{2}}\right\rfloor$.
\pause
  同理可得， $k_{3}=\left\lfloor\frac{n}{p^{3}}\right\rfloor$ 等。 
  \pause
  当我们求和$k_1+k_2+\cdots$时，$1$到$n$之间形如$m=p^kq$ ($(p,q)=1$) 的整数$m$恰好被计数了$k$次，
  这也是因子$m$对$n!$的$p$-进赋值的贡献。
  \pause
  故 $n!=1 \cdot 2 \cdot 3 \cdots n$ 中 $p$ 的指数为 $v_{p}(n!)=k_1+k_{2}+k_{3}+\cdots$, 即得定理。
\pause
  这是一个有限和，因为 $1,2, \cdots, n$ 不会含因子 $p^{n}$.
\end{proof}


定理 3 由 Tchebycheff (切比雪夫)在 1852 年证明。 这些结果关联于著名的素数定理，即
\[
\frac{\pi(x)}{x / \log x} \rightarrow 1 \quad \text {(当~} x \rightarrow \infty).
\]
也等价于 $\theta(x) / x \rightarrow 1$ (当 $x \rightarrow \infty)$. 另一种表述是定义函数 $\displaystyle\operatorname{li} x=\int_{2}^{x} \frac{\mathrm{d} t}{\log t}$, 则
\[
\frac{\pi(x)}{\operatorname{li} x} \rightarrow 1 \quad(\text {当~} x \rightarrow \infty).
\]
这是因为， 由 L' Hôpital (洛必达) 法则有
\[
  \lim _{x \rightarrow \infty} \frac{\operatorname{li} x}{x / \log x}=\lim _{x \rightarrow \infty} \frac{1 / \log x}{1 / \log x-1 / \log ^{2} x}=\lim _{x \rightarrow \infty} \frac{\log x}{\log x-1}=1.
\]
\end{frame}

\begin{frame}



\begin{comment*}%评述
素数定理由少年 Gauss 首先猜出，到 1896 年由 J. Hadamard（阿达马) 和 De la Vallée-Poussin 独立证明， 用 Riemann zeta 函数的复解析性质。 1948 年， A. Selberg 给出了著名的“初等证明”, 即不用复分析理论。

有关素数分布的另一个著名定理， 是 Dirichlet (1837)算术数列定理： 对互
素的正整数 $a, b$, 算术序列 $a n+b$ ( $n$ 取遍正整数) 中有无限多项是素数。 例如 $4 n+3$ 型素数有无限多。

不过在素数分布方面， 更多的是长期未解决的问题。 例如， $n^{2}+1$ 型素数是否有无限多? $2^{n}+1$ (Fermat), 或 $2^{n}-1$ (Mersenne)型素数是否有无限多? 等等。

另一个著名的未解决问题是 Goldbach (哥德巴赫)猜想 (Goldbach's conjecture): 每个偶数 $n(\geqslant 4)$ 均是两个素数之和， 即可表为 $n=p_{1}+p_{2}\left(p_{1}, p_{2}\right.$ 为素数). 被简称为 $1+1$ 问题。 例如： $8=3+5,16=3+13$, 等等。 在这个方向上， 目前世界上最好的结果， 还是我国数学家陈景润在 1973 年， 在极端困难复杂情势之下艰苦卓绝奋斗不息， 所得到的曾誉满神州激励一代人的结果： 充分大的偶数 $n$ 均可表示为 $n=p+q$ ( $p$ 为素数， $q$ 为素数或两个素数之积). 此结果被简称为 $1+2$. 而 Vinogradov (维诺格拉多夫)在 1937 年证明了： 充分大的奇数 $n$ 均可表示 3 个素数之和。

我国数学家张益堂经过艰苦执著的长期追求， 在“孪生素数”相关问题上取得巨大成果， 在 2013 年 4 月证明了 “存在无数对相邻素数， 它们之间的差不过7000 万”. 到 2014 年 2 月， 7000 万已被人改进到 246. 如果这一常数改进到 2, 就证明了孪生素数猜想。 天才数学家陶哲轩 (Terence Chi-Shen Tao, 1975-)也证明了素数间隔问题的 Erdös(爱尔迪希， Paul Erdös)猜想。
\end{comment*}

\end{frame}
